package com.mxw.算法之美.a18动态规划;

/**
 * @author Administrator
 * @create 2024/8/8 15:37
 */
public class a01Dynamic {

    /**
     * 最短路径：
     * 每个阶段都有向右走或者向下走两种决策，并且每个阶段都会对应一个状态集合。
     * 前面阶段的状态确定之后，不会被后面阶段的决策所改变。
     * 当前位置可以通过前面的位置推导出来。
     * <p>
     * 状态转移表法：
     * 1.先用简单的回溯算法解决，然后定义状态，每个状态表示一个节点，对应画出递归树、
     * 2.从递归树中，是否存在重复子问题，以及重复子问题是如何产生的。
     * 3.找到重复子问题，加备忘录解决
     * <p>
     * 状态表一般都是二维的。每个状态包含三个变量，行，列，数组值。
     * 根据决策先后过程，从前往后，根据递推关系，分阶段填充状态表中的每个状态。
     * 将这个递推填表的过程，翻译成代码。
     * <p>
     */

    private int minDist = Integer.MIN_VALUE;


    //int[][] w n*n 矩阵  1.回溯算法穷举所有的走法
    public void minDistBT(int i, int j, int dist, int[][] matrix, int n) {
        if (i == n && j == n) {
            if (dist < minDist) {
                minDist = dist;
            }
            return;
        }
        if (i < n) {
            // 往下走，更新i=i+1,j=j
            minDistBT(i + 1, j, dist + matrix[i][j], matrix, n);
        }
        if (j < n) {
            // 往右走，更新i=i,j=j+1
            minDistBT(i, j + 1, dist + matrix[i][j], matrix, n);
        }
    }

    // 递归树，发现存在重复子问题。

    // 二维状态表，行,列标识棋子所在的位置。表中的数值标识从起点到这个位置的最短路径，
    // 通过不断的状态递推演进，按行来依次填好状态表
    public int minDistBT(int[][] matrix, int n) {
        int[][] states = new int[n][n];
        int sum = 0;
        for (int j = 0; j < n; j++) {
            // 初始化第一行数据
            sum += matrix[0][j];
            states[0][j] = sum;
        }
        sum = 0;
        for (int i = 0; i < n; i++) {
            // 初始化第一列数据
            sum += matrix[i][0];
            states[i][0] = sum;
        }

        // 递推填表
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                // 状态转移方程
                states[i][j] =
                        matrix[i][j] +
                                Math.min(states[i][j - 1], states[i - 1][j]);
            }
        }

        return states[n - 1][n - 1];

    }


}
